package leetcode.code0029;

public class Solution1 extends Solution29 {

	@Override
	public int divide(int dividend, int divisor) {
		if (dividend == divisor) {
			return 1;
		}
		int min = 0;
		if (dividend == Integer.MIN_VALUE) {
			if (divisor == sub(0, 1))
				return Integer.MAX_VALUE;
			if (divisor == 1)
				return Integer.MIN_VALUE;
			if (divisor == Integer.MAX_VALUE)
				return sub(0, 1);
			min = 1;
			dividend = add(dividend, min);
		}
		if (divisor == Integer.MIN_VALUE || divisor == Integer.MAX_VALUE)
			return 0;
		int a = dividend > 0 ? dividend : add(~dividend, 1);
		int b = divisor > 0 ? divisor : add(~divisor, 1);
		int ans = 0;
		for (int i = 31; i >= 0; i = sub(i, 1)) {
			if ((a >> i) >= b) {
				ans = add(ans, 1 << i);
				a = sub(a, b << i);
			}
		}
		if (min != 0) {
			a = add(a, min);
			if (a >= b) {
				ans = add(ans, 1);
			}
		}
		if ((dividend ^ divisor) < 0) {
			return add(~ans, 1);
		} else {
			return ans;
		}
	}

	public int add(int a, int b) {
		do {
			int carry = (a & b) << 1;
			a = a ^ b;
			b = carry;
		} while (b != 0);
		return a;
	}

	public int sub(int a, int b) {
		return add(a, add(~b, 1));
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
		so.debug6();
		so.debug7();
	}

}
